#include "Tree.h"

//declaration of static members
vector<Tree*> Tree::GetTree[2]; 

Tree::Tree()
{
	Size = 0;
	data = new Node();
	heavyChild = NULL;
	GetTree[0].push_back(NULL);
	GetTree[1].push_back(NULL);
}

Tree::Tree(Node* data1)
{
	Size = 0;
	data = data1;
	heavyChild = NULL;
}


Tree::~Tree()
{
	if (data != NULL)
		data->~Node();
	children.~deque();
	heavyChild = NULL;
}

void Tree::AddLeftTree(Tree* T)
{
	children.push_front(T);
}

void Tree::AddRightTree(Tree* T)
{
	children.push_back(T);
}

Tree* Tree::getLeft() const
{
	if(!children.empty())
		return children.front();
	return NULL;
}

Tree* Tree::getRight() const
{
	if(!children.empty())
		return children.back();
	return NULL;
}

void Tree::ClearHeavyPath()
{
	Tree* tmp=this;
	while(tmp != NULL)
	{
		tmp->getData()->setHeavy(false);
		tmp=tmp->getHeavy();
	}
}


/* postorder traversal to fill the size of ALL subtrees.
then, second pass from root to leave to mark heavy path
and fill HeavyPath & TopLight Arrays
*/
void Tree::FindHeavyPath()
{
	Tree* tmp = this;
	bool flag = true;

	
	while (flag)
	{
		tmp->data->setHeavy(true);

		if ( tmp->getLeft() == NULL )
			flag = false;
		else
		{
			int max=0,index,maxIndex=0
				,childrenSize=tmp->children.size();
			for(index=0; index < childrenSize; index++)
			{
				if(tmp->children.at(index)->getSize() > max)
				{
					max=tmp->children.at(index)->getSize();
					maxIndex=index;
				}
			}
			tmp->heavyChild = tmp->children.at(maxIndex);
			tmp = tmp->children.at(maxIndex);
		}
	}
}

void Tree::SelectRightHeavyPath()
{
	Tree* tmp=this;
	while(tmp != NULL)
	{
		tmp->data->setHeavy(true);
		if(!tmp->children.empty())
			tmp->heavyChild = tmp->children.back();
		else
			tmp->heavyChild = NULL;
		tmp = tmp->heavyChild;
	}
}

int Tree::Postorder()
{
	int i, childrenSize=children.size();
	
	Size=0;
	for(i=0; i < childrenSize; i++)
	{
		Size+=children.at(i)->Postorder();
	}
	Size+=children.size();

	if ( getLeft() == NULL )
		Size = 0;
	return Size;
}

void Tree::PostOrderUpdateGetTree(int treeIndex, bool countTemp)//countTemp is true by defualt
{
	static int count;
	int i, childrenSize = children.size();
	if(countTemp)
	{
		count=1;
		GetTree[treeIndex].push_back(NULL);
	}
	for(i=0; i < childrenSize; i++)
	{
		children.at(i)->PostOrderUpdateGetTree(treeIndex, false);
	}

	data->setIndex(count++);
	GetTree[treeIndex].push_back(this);
}


void Tree::Save(string filename) const
{
	ofstream myfile(filename.c_str());
	SaveRec(myfile);
	myfile.close();
}

void Tree::SaveRec(ofstream &myfile) const
{
	unsigned int i;
	myfile<<"("<<data->getLabel();
	for( i=0 ;  i<children.size() ; i++)
	{
		getChild(i)->SaveRec(myfile);
	}
	myfile<<")";
}

bool IsForest(string &line)
{
	int index(0),counter(0),NumOfTrees(0);
	while(line[index]!='\0')
	{
		if(line[index] == '(')
			counter++;
		if(line[index] == ')')
		{
			counter--;
			if(counter==0)
				NumOfTrees++;
		}
		index++;
	}
	if(NumOfTrees>1)
		return true;
	else
		return false;
}

Tree* Load(string& filename)
{
	Tree* retValue;
	string line;
	bool isForest;
	ifstream myfile(filename.c_str());
	getline(myfile , line);
	if(line == "")
		return NULL;
	ClearSpaces(line);
	isForest = IsForest(line);
	if(isForest)
	{
		retValue = new Tree(new Node(EMPTY_LABEL,false));
		LoadRecForest(line,retValue);
	}
	else
	{
		retValue = LoadRecTree(line , true);
	}
	myfile.close();	
	return retValue;
}


void LoadRecForest(string& line, Tree* root)
{
	Tree* newNode = LoadRecTree(line , true);
	while(newNode->getData()->getLabel() != "")
	{
		root->AddRightTree(newNode);
		newNode = LoadRecTree(line , false);
	}
}

Tree* LoadRecTree(string& line, bool init)
{
	static int index;
	string label("");
	if(init)
		index = 0;
	if(line[index] == '\0')
		return new Tree( new Node("" , false));
	if(line[index]=='(')
		index++; // skip '('
	while(line[index] != ')' && line[index] != '(')
	{
		label += line[index++];
	}
	Tree* newNode = new Tree( new Node(label , false));
	while(line[index]!=')')
	{
		newNode->AddRightTree(LoadRecTree(line , false));
	}
	if(line[index]==')')
		index++; // skip ')'
	return newNode;
}

void ClearSpaces(string& line)
{
	int start,i(0),count(0);
	while(line[i] != '\0')
	{
		if(count == 0)
			start=i;
		if(line[i] == ' ' || line[i] == '\t')
			count++;
		else
		{
			if(count > 0)
			{
				line.erase(start,count);
				i = start;
				count=0;
			}
		}
		i++;
	}
	if(count > 0)
		line.erase(start);
}

string ItoS(int num)
{
	string s;
	if(num == 0)
		return "0";
	while(num != 0)
	{
		s.insert( s.begin(), '0'+num%10);
		num/=10;
	}
    return s;
}

